We construct (k+-1)-regular graphs which provide sequences of expanders byadding or substracting appropriate 1-factors from given sequences of k-regulargraphs. We compute numerical examples in a few cases for which the givensequences are from the work of Lubotzky, Phillips, and Sarnak (with k-1 theorder of a finite field). If k+1 = 7, our construction results in a sequence of7-regular expanders with all spectral gaps at least about 1.52.
展开▼
